Abstract
We present
in this paper a new multi-user receiver using a Genetic Algorithm (GA) based
decision scheme for interference suppression in Direct Sequence Code Division
Multiple Access Wireless Systems (DS-CDMA). In this work a hybrid approach that
employs a GA and Multi-user Detector for the multi-user detection (MUD)
problems in CDMA/WCDMA cellular systems is investigated. The proposed GA
approach with MUD performs well in the presence of Multiple Access Interference
(MAI) under CDMA/WCDMA standard conditions. Cancellation of MAI is the prime
concern in our work since it improves the performance of the system with
increasing number of users. This paper also compares the performances of MUD
using Neural Networks and GA with the standard optimum receiver which is a
benchmark for synchronous CDMA systems. Simulation results for these above
methods are provided to show that the approach is promising and encouraging. A
comparative performance analysis of the four receivers, i.e. conventional,
optimum, neural network, and genetic algorithm is carried out by simulations.
In all examples considered, the proposed genetic receiver outperforms the
neural network receiver.
Keywords
Code division multiple access (CDMA), Genetic
algorithm (GA), Multiple access interference (MAI),
Multi-user detection (MUD), Neural networks.
Introduction
CDMA is one of the several methods of multiplexing
that has taken a significant role in cellular and personal communication
systems. Direct-sequence CDMA is the most popular one and has unique feature
that each user is assigned a different signature waveform, and the received
signal will be the superposition of the signals transmitted by each of the
users. The capacity of the DS-CDMA system is limited by multiple access
interference. Two main approaches have been developed to reduce or suppress
MAI. The first approach is by virtue of multi-user detection in which the
differences of the spreading sequences of the users are employed to remove MAI.
Another approach is to suppress MAI. MUD is the intelligent
estimation/demodulation of transmitted bits in the presence of multiple access
interference.
MUD technique is an appropriate one for suppressing
the effects from the multiple access interference and consequently improving
the system performance [1]. The problem of demodulating signal in a code
division multiple access - Additive White Gaussian Noise (AWGN) channel is
known as MUD. Multiple accessing in the code domain is achieved by spreading
the spectrum of the transmitted signals using preassigned code waveforms. The
conventional method of demodulating a spread spectrum signal in a multiuser
environment employs one matched filter to the desired signal [1]. Since the
conventional receiver ignores the presence of interfering signals it is reliable
only when there are a very few simultaneous transmissions. Due to MAI, the
single user detection strategy induces a problem by the name of Near-far
problem, i.e. the performance drops when the powers of the transmitting users’
are dissimilar [1]. Thus cancellation of MAI is necessary to improve the
performance. This requires the so called multiuser strategy.
The optimum MUD outperforms with a marked increase in
computational complexity, which is exponential in the number of users [2]. With
the already existing decorrelating detector also, it has been proven that the
complexity is exponential in the number of users. Since CDMA systems could
potentially have a large number of users, this solution may prove, in a number
of situations, to be impractical and too expensive to be implemented. This
situation gave rise to suboptimal detectors that are near-far resistant and
have less complexity, and their performance is comparable to that of optimum
receiver. One is the decorrelating detector and the other one the multistage
detector (MSD). The decorrelating detector is linear and near-far resistant. It
provides significant improvement over the conventional one, at conditions where
the MAI is dominant. MSD is a non-linear detector that might achieve near optimal
performance in some cases. In contrast to the decorrelating detectors, it
requires exact knowledge of the user’s powers. It relies on improving each
stage by stage estimate by subtracting the estimate of the MAI obtained by the
previous stage. The decorrelating detector suffers from noise enhancement and
the MSD performance depends upon the initial estimate, which is generally
provided by the common detectors.
In this paper, we consider the multiuser detection
from a combinatorial optimization point of view by neural and genetic approach.
Driven by the demand of algorithms to attain lower computational complexity,
here we have proposed a neural net multiuser receiver and genetic multiuser
detector [3][4]. It is worth mentioning that the
multiuser detector can be viewed as an optimizer that searches for a better
solution. We also present the neural net receiver for the demodulation of
multiuser signal in the presence of MAI and have shown that it gives a near optimum
performance. The algorithm employed is the back propagation methodology to
train the network. Next the GA approach is considered which operates on the
population of potential solutions (called generation) and uses a function to
produce increasingly better approximations to the solutions. At each iteration,
a new set of possible solutions is created by selecting individuals based on
the fitness level and applying the generic operators, crossover and mutation.
It may be computationally expensive, but can be parallelized in both of these
approaches.
The paper is organized as follows: The general CDMA
model, the conventional, optimum, decorrelating detector, are presented. The
neural net model is explained and the neural net receiver which employs the
matched filter section with a sandwich concept is presented. The genetic model
is presented as an optimal technique. Further we have highlighted the
computational complexity of the detectors. Computer simulations are
highlighted. Finally, concluding remarks are pointed out motivating research
for other near-far resistant and near-optimal methodologies.
Approach
and Methods
Multi User
CDMA System Model
Let us assume that there are K transmitters in the
network at a given time interval. The kth
user transmits a signal derived from a set of code waveforms assigned to the
corresponding user. In this model we consider only symbol synchronous CDMA
model which is time limited in the interval [0,T] where T is symbol duration,
and the packet length is considered to be P. In a multi user model the signal
at a given receiver is the superposition of the K transmitted signals in
additive channel noise
(1)
where, n(t) is
the white Gaussian noise with spectral density No/2 .s(t,b) which
is the signature waveform that is time limited to [0, Tb], expressed
as
(2)
where, b =[ b1(1),
b2(1),… bK(1),],
[ b1(2), b2(2),…
bK(2),]…… =[ b1(P), b2(P),…
bK(P),] , bk
ε { +1,-1} is the ith transmitted bit
of the kth user., sk(t)
is the signature sequence of the kth user,
Tb is the bit interval duration , τk
ε { 0,Tb} is the
time delay of the kth user, P is the
packet size.
The modeling of symbol synchronous system, is
considered, since it will provide a manageable complexity for problem solution
with the optimization method such as GA and Neural networks, and help
understand better, the issues of the asynchronous case which is further complex
and general.
Conventional
Matched Filter
The system model for Conventional Matched Filter
(CMF), which is also generally called as Matched Filter (MF) will be given as
below for a single user [3].
(3)
Where the first term indicates the desired users
signal and the second one indicates multiple access interference and the third
one being noise. The CMF treats all the terms except the first one as noise on
the whole and that is the reason for the CMF with poor performances in Bit
Error Rate (BER) with more number of users.
For all the users the detection becomes as follows:
In matrix notation we have,
Y = RAb + n
The decision scheme provided by the CD is given as
follows from the above equation ie;
bCD(i) = sign { y(i) }
where, i denotes the ith user bit.
Optimum
Detector
The optimum multiuser detector is an enhanced version
of CD which searches for the best solution in an optimal sense. The optimal
detector decides the bit sequence as the one that minimizes the following
equation.
(4)
The above equation considers the error in the mean
squared sense. The minimization of the above equation results in the following
detection decision.
(5)
In this equation b indicates the possible combination
of input vectors that could have been possibly be sent at the transmitter and y
denotes the actual received bit vector. It is clear from the above that the
optimization is over the 2PK combination of vectors and it is
obvious that the error computation complexity is having exponential relation
with the number of users.
Neural
Networks in Multiuser Detection
Artificial neural networks are highly interconnected
networks of simple processing units referred to as nodes or perceptrons
which operate in parallel [3]. They are designed to mimic the neurobiological
networks. Particularly the multi layer perceptron, which is a layered network
of perceptrons, is capable of approximating arbitrary
decision regions in the input space for most classification problems. Also the
possibility of the massive parallelism makes them a desirable alternative for
optimum and conventional receivers in multiple access communications. An
important aspect of neural network design is the modification rule for
training. The back propagation algorithm is an excellent example of training
algorithms that have been widely used to many
classification problems.
In our problem, the neural network is used as the bit
classification scheme in the synchronous channel. The configuration of neural network
used here are for single user demodulation. The configuration is given in the
following figure.
Figure 1.Perceptron model
The network shown here consists of an input layer of
nodes and hidden layer and an output layer of nodes. The basic mathematical
model of each neuron or node is given as the output of the ith node of l th layer takes
the value as,
(6)
where Ml denotes the number of nodes in l th layer
and wji(l) denotes the weights associated with the
connection between the jth
node of the l-1st layer to he ith node of the l th layer and w0i(l) is the corresponding threshold. The activation
function used here are tan sigmoid function in the hidden layer and pure linear
function at the output layer. In this model v
j(0) denotes
the jth
input to the network and M0 is the total number of inputs to the
network.
Figure 1 shows a simple multi layer perceptron with 3
inputs and a single output. The dot symbol denotes the summation function from
all the prior connections. In multi user detection problems the number of nodes
in the output layer will be equal to K’ where K’ ε {0, 1, 2…K} is the
number of demodulated signals. The training algorithm used here is back
propagation algorithm which is an iterative gradient descent algorithm that
minimizes an empirical error function.
The error function is defined as the sum of errors
due to each training input pattern ε (ω) = ∑p ε
s where the error corresponding to the pth training pattern is defined
as ½ ∑i ( di – vi(L) )2
where di is the ith
desired output specified by the user. In general because of redundancy of
neural networks, the back propagation algorithm will find only a local minimum
of the error surface. The back propagation is better at training the neural networks
for single user detection problem. The performance of this algorithm is
improved by making the learning procedure under supervisory mode in the hidden
layer.
Genetic
Algorithm in Multiuser Detection
GA are search algorithms
based on the mechanics of natural selection [5]. In every generation a new set
of creatures (such as bit strings) are being generated which have survived from
the previous generation The basic application of GA is to reach the optimum
point of a search space with the minimal overheads of time and storage and
computational complexity with some trade off in reaching the exact global
minima in the given optimization problem. GA is an effective tool for searching
the surface to reach the global minima.
The basic GA starts with a population of bit strings
called chromosomes in GA parlance, which undergoes the GA evolution for given
number of generations and finally ends up with the best population from which
the most capable individual for our problem can be chosen. The population size
generally does not change over time .i.e. there is no generation gap or in
other words the population size is kept constant over all generations. If some
generation gap is introduced for example say as 0.1, then
the population size will keep on decreasing by the same amount between each
generation. Moreover the population size and chromosome length are problem
specific. The members of the population are the individual symbol strings that
represent possible solutions to the problem to be solved. The GA evolution
process is defined by three operations: 1.Selection 2. Crossover 3.Mutation
Each member of the population is evaluated for its
fitness value and assigned a probability to be selected for reproduction. After
selection the recombination or crossover is applied to pairs of parents to
create offsprings which will be mutated through the mutation operator and
inserted into new population forming the next generation of individuals. The
individuals here implies one of the possible solution candidates. The fitness
values of individuals are evaluated after each mutation and the least fit
individuals are replaced by new individuals. The algorithm continues until good
results are obtained in terms of the objective function.
In terms of the problem at hand, the problem
representation and the related issues are addressed as follows. The main
variable to be optimized is the detected bits of the users at the receiver. The
received bits will be noisier and the solution candidates are in the form of
bit strings in which each bit represents the user bit. The solution candidates
are evaluated along with the received noisy bits to arrive at the near optimal
value. The solution candidates are in the
form of binary strings already as {-1,
+1} as the bits are antipodally modulated at the
transmitter for synchronization issues. Hence no further encoding procedures
are needed.
Also the initial population of solutions is taken
from the conventional detector outputs. With the one single CD decision output,
the individual bits are randomly modified to obtain a new set of solution
candidates from the CD decision set. The purpose of the fitness function is to
evaluate the individuals of the population. It is required to be a non-negative
figure of merit [5], which otherwise may introduce errors in finding out the
least fit individual in each generation. In MUD the objective is maximization
of the cost or objective function derived from optimal detection problem as
given below:
c(b) =
2 yT
b - bT H b (7)
The mapping of the objective
function into a non negative function is done as follows.
f(b) = K +
{ c(b) - cw } (8)
Where cw is the
objective value of the worst individual in the current population and K is a
positive arbitrary constant.
GA parameters
varied are:
1. Population size,2. Selection mechanism,3. Type of
crossover 4. Crossover probability,5. Mutation probability,6. Replacement
strategy. The simulation results shown were given with detailed settings of
these parameters.
Complexity
Of These Detectors
In the optimum multiuser detector, the search
included over the entire 2 PK possible
combinations. However, as the number of users increases the comparison process
is unmanageable. The alternative to the direct optimality computation is
through dynamic programming [6] for example, in which the number of comparisons
is not dependent on packet sizes of the bits. But even in that implementation
the solution will not be NP-hard for moderate values of K, and hence a
heuristic algorithms for optimization like GA will definitely be a good
alternative [7]. While other optimization methods have their own properties on
closing onto the global minimum, GA always approach towards global minimum and
in terms of local minima search, it approaches the minimum quite fast than
other methods. The computation complexity of GA is given in terms of Np the number of population in each generation and
Ng, the number of generations involved in the search. The following
are the calculations involved in the GA process.
1. Random sequence generation for Np
individuals for each generation, for the selection process.
2. Since the number of crossovers is Np/2,
the bit string exchanges taking place at the rate of pcNp/2
where pc is the cross over
probability.
3. The number of mutations are NpPK,
taking the number of bit inversions taking place for mutation to pmNpPK, where P is the packet size
and K is number of users, and pm is the mutation probability.
Arriving at the computations per bit resulting in the computational complexity
of O(NgNp). And this compares
well with the dynamic programming alternative for optimization.
Results
The simulation for a 10-user and a 3-user system are
taken for illustration. The PN sequences used were of 15 bit gold sequences.
The gold sequences are generated by modulo-2 addition of two m-sequences
clocked by the same chip clock. In contrast to simple m-sequences, gold
sequences are suitable for multi-user CDMA systems. They offer a large number
of sequence sets with good correlation properties. The autocorrelation of the
sequences are found to be satisfying the properties of pseudo noise sequences
in terms of auto correlation. The synchronous system model was considered.
There were two types of results obtained. One is SNR vs. BER and the other is MAI vs. BER. The
first result was plotted for both user configurations against all four methods
namely the CD, optimal detector, neural net detector and the GA receiver. The
plot of MAI vs. BER is presented in which the MAI is represented as the ratio
of the first user’s signal power with that of other users’ signals whose
increase in dB indicates the presence of strong signals of other users while
detecting the first users’ signal. The Signal to Noise ratio (SNR) for MAI plot
was maintained at Eb/No = 6 dB. Eb/No
ratio signifies the SNR value of the user’s signal which is kept constant. The
received powers of all users are assumed to be equal for the SNR plot. The
following were the parameters used for the neural network model:
No. of input layers – 10 / 3 , No of Hidden
layers – 7 / 3, No. of output layer – 1
(single user detection) Transfer functions used
– tan sig (hidden layer) purelin (output layer)
Training method - back propagation ,
Simulation bits - 500 bits. The
layers are given for 10 and 3 user configurations.
|
Parameter |
Value |
|
Selection |
Roulette |
|
Crossover type |
Single point |
|
Crossover probability |
0.98 |
|
Mutation
type |
Boundary mutation |
|
Mutation probability |
0.01 |
|
No. of generations |
10 |
|
Population size |
10 |
Table 1 – GA parameters
Figure.2 Simple GA Model
Figure.3 – MAI vs BER NN Vs GA
Figure.4 – MAI vs. BER
K =3,L
=15 ,Bits =500 K
=3,L =15 ,Bits =500
Figure.5 – MAI vs. BER Figure.6. – SNR vs. BER
K =10, L
=15, Bits =500 K =3, L = 15, Bits = 500
Figure 7 – SNR vs. BER
K =10, L = 15, Bits =500
Discussion
The results shows the comparison of BER in terms of
signal to noise ratio as well as multiple access interference which is
represented as the ratio of energy of first user with the energy of all other
users. i.e. Ei/E1 ratio. The energy of all other users
are taken to be equal when compared to the first user.
The CD tends to perform well at lesser number of users and is found to be ideal
for such situations with lesser complexity. Whereas for the 10 user scenario
depicted in Figure 5 indicates the genetic method performs better than the
neural network based detector performance for more number of users. For the 3
user case the GA performs better in terms of BER than the Neural Network. The
optimum detector forms the bench mark performance levels against MAI and the
same is shown in Figure 4 along with the methods that are being discussed viz.
neural network and GA based detectors. The performance of 3 user case is
projected in Figure 3 and Figure 4 for MAI and Figure 6 for SNR Vs BER.
In terms of complexity, the neural network structure
implemented requires very high memory for storage of multi layer perceptron
models with much larger number of users whereas the genetic structure needs comparatively
lesser memory but with higher processing requirements. Hence when comparing GA
with the neural networks the GA, gives better performance to that of neural
network, which can be used for implementation with lesser overhead than that of
the neural network method.
Conclusion
On comparing the performances of the sub optimal
detection techniques, it is shown that the conventional detector scores well at
lesser user scenarios with its minimum complexity. For more number of users,
the optimum detector gives the best results. However its exponential relation
of complexity with number of users makes it practically unrealizable. Here, it
is shown that the GA performs better than the neural network and also has the
implementation possibilities with the current parallelism available in
computers.
Acknowledgements
The authors would like to thank their supervisor, and
those who actively supported in carrying out simulations for various
configurations. The authors are also thankful to the staff of the department
who gave very useful comments and conceptual clarifications during the course
of this work. The author Mr. B. Sivakumar would like
to thank his parent college, Dr.Ambedkar Institute of
Technology,
References
[1] Lupas.R. Verdu.S. Jan.1989. Linear Multiuser
Detectors for Synchronous Code-Division Multiple-Access Channels, IEEE
Transaction on Information Theory, vol. 35; no. 1; pp. 123-136.
[2] Verdu.S. 1989. Computational Complexity of
Optimum Multiuser Detection. Algorithmica
vol. 4; no. 3; pp. 303-312.
[3] Aazhang.B. Paris.P. and Orsak.C. July 1992. Neural Networks for Multiuser
Detection in Code-Division Multiple Access Communications, IEEE Transactions on Communications, Vol.40; No.7.
[4] Ergun.C and Hacioglu.K.
Aug.2000. Multiuser Detection Using
a Genetic Algorithm in CDMA Communication Systems. IEEE Transactions on Communications, Vol.48; No.8.
[5] Goldberg.D.E., 1989. Genetic
Algorithm in Search, Optimization, and Machine Learning.
[6] Verdu. S, Jan 1986. Minimum Error probability for
Asynchronous Gaussian Multiple Access Channels, IEEE Transaction on Information
Theory, Vol. IT-32; pp 85-96.
[7] Wesley.L.A.1998.Integer
Programming,
Technical College - Bourgas,